#include <iostream>
#include "SortAlgorithms.h"

using namespace std;

void InsertionSort::Sort(int *inputArray, int size)
{
        int key;
        int i;
        for(int j = 1; j < size; j++)
        {
                key = inputArray[j];
                i = j - 1;
                //compare everything to the left of they key with the key
                //if there is nothing to the left of the key left, or if the key is >= to its left neighbor 
                //then move the current key the next over to the right(the movement is done in the j loop)
                while(i >= 0 && inputArray[i] > key)
                {
                        //if the key was smaller than something to the left of the key, then move that thing to the right of the key
                        //everything to the left of they key that is bigger than the key is moved up one position until they key finds its place
                        inputArray[i + 1] = inputArray[i];
                        //check the next thing to the left
                        i = i - 1;
                }
                
                //this line does two things. if we never got in the while loop, it basically does nothing since line 12th set the key to j(i+1)
                //however if we got in the loop, then this line will put the key in its right position
                inputArray[i + 1] = key;
        }
        
        return;
}
